package leetcode.editor.cn;

/**
 * @id: 50
 * @title: Pow(x, n)
 */
 
//实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 2.00000, n = 10
//输出：1024.00000
// 
//
// 示例 2： 
//
// 
//输入：x = 2.10000, n = 3
//输出：9.26100
// 
//
// 示例 3： 
//
// 
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2-2 = 1/22 = 1/4 = 0.25
// 
//
// 
//
// 提示： 
//
// 
// -100.0 < x < 100.0 
// -231 <= n <= 231-1 
// -104 <= xn <= 104 
// 
// Related Topics 递归 数学 
// 👍 823 👎 0

public class P50PowxN {
    public static void main(String[] args) {
        Solution solution = new P50PowxN().new Solution();
        // todo
        final double v = solution.myPow(2, -2147483648);
        System.out.println(v);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 快速幂
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? qPow(x, N) : (1.0 / qPow(x, -N));
    }

    private double qPow(double x, long n) {
        if (x == 1 || n == 0) {
            return 1;
        }
        double pow = 1;
        // n=11 => n=1011
        // pow = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1 = 11
        while (n > 0) {
            // 对2求余就是获得1011的最后一位
            // 1011(11) % 2 = 1 （二进制低位）
            // 101(5) % 2 =1
            // 10(2) % 2 = 0
            // 1(1) % 2 = 1  （二进制高位）
            if (n % 2 == 1) {
                pow *= x;
            }
            x *= x;
            // 右移1就是除2
            // 11/2 -> 5
            // 5/2 -> 2
            // 2/2 -> 1
            // 1/2 -> 0 退出循环
            n >>= 1;
        }
        return pow;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}